class Solution:
    def minimumCost(
        self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        horizontalCut.sort(reverse=True)
        verticalCut.sort(reverse=True)
        cost = 0
        cut_row, cut_col = 0, 0
        # 当有某个方向还没切完所有刀数
        while cut_row < m-1 or cut_col < n-1:
            if cut_col == n-1 or (cut_row < m-1 and horizontalCut[cut_row] > verticalCut[cut_col]):
                cost += horizontalCut[cut_row] * (cut_col + 1)
                cut_row += 1
            else:
                cost += verticalCut[cut_col] * (cut_row + 1)
                cut_col += 1
        return cost

if __name__ == "__main__":
    s = Solution()
    print(s.minimumCost(m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]))
    print(s.minimumCost(m = 2, n = 2, horizontalCut = [7], verticalCut = [4]))